# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

    def print(self, level):
        prefix = " " * level
        return "{}{}\n".format(prefix, self.val) + (self.left.print(level+1) if self.left else "") + (self.right.print(level+1) if self.right else "")

    def __str__(self):
        return self.print(0)

    def __rper__(self):
        return self.print(0)

class Solution(object):
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        indexDict = {}
        for i in range(len(inorder)):
            indexDict.update({inorder[i]:i})
        def build(pbegin, pend, ibegin, iend):
            if pbegin==pend:
                return None
            node = TreeNode(preorder[pbegin])
            if pend-pbegin==1:
                return node
            i = indexDict[preorder[pbegin]]
            leftLength = i-ibegin
            rightLength = iend-(i+1)
            node.left = build(pbegin+1, pend-rightLength, ibegin, ibegin+leftLength)
            node.right = build(pend-rightLength, pend, iend-rightLength, iend)
            return node
        return build(0, len(preorder), 0, len(inorder))

print(Solution().buildTree([1,2], [1,2]))
